package com.gaofeng.algo.kt

import java.util.*

fun main() {
    testInternals()
}

private fun testInternals() {
    val intervals = arrayOf(intArrayOf(1, 2), intArrayOf(2, 4), intArrayOf(1, 3))
    val result = eraseOverlap(intervals)
    println("kotlin result:$result")
}

private fun findContentChildren(children: IntArray, cookies: IntArray): Int {
    Arrays.sort(children)
    Arrays.sort(cookies)
    var child = 0
    var cookie = 0
    while (child < children.size && cookie < cookies.size) {
        if (children[child] <= cookies[cookie]) {
            child++
        }
        cookie++
    }
    return child
}

fun candy(ratings: IntArray): Int {
    val size = ratings.size
    val candys = IntArray(size)
    Arrays.fill(candys, 1)
    for (i in 1 until size) {
        if (ratings[i] > ratings[i - 1]) {
            candys[i] = candys[i - 1] + 1
        }
    }
    for (i in size - 1 downTo 1) {
        if (ratings[i - 1] > ratings[i]) {
            candys[i - 1] = Math.max(candys[i] + 1, candys[i - 1])
        }
    }
    var total = 0
    for (i in 0 until size) {
        total += candys[i]
    }
    return total
}

/**
 * 遍历过程中,每一次的决策都是最优的,一直到结束,结果也是最优的.
 * 保证花的相邻位置都没有种花,那么就将其种上花,并将指针往后移一位.
 */
private fun canPlaceFlowers(flowerbed: IntArray, n: Int): Boolean {
    var count = 0
    var i = 0
    while (i < flowerbed.size) {
        if (flowerbed[i] == 0 && (i == 0 || flowerbed[i - 1] == 0) && (i == flowerbed.size - 1 || flowerbed[i + 1] == 0)) {
            flowerbed[i++] = 1
            count++
        }
        if (count >= n) {
            return true
        }
        i++
    }
    return false
}

fun findMinArrowShots(points: Array<IntArray>): Int {
    val size = points.size
    if (size == 0) {
        return 0
    }
    Arrays.sort(points, Comparator.comparingInt { o: IntArray ->
        o[1]
    })
    var total = 1
    var start: Int
    var end: Int
    var pre = points[0][1]
    for (p in points) {
        start = p[0]
        end = p[1]
        if (start > pre) {
            total++
            pre = end
        }
    }
    return total
}

private fun eraseOverlap(internals: Array<IntArray>): Int {
    if (internals.isEmpty()) {
        return 0
    }
    val size = internals.size
    Arrays.sort(internals) { o1, o2 -> o1[1] - o2[1] }
    var total = 0
    var pre = internals[0][1]
    for (index in 1 until size) {
        if (internals[index][0] < pre) {
            total++
        } else {
            pre = internals[index][1]
        }
    }
    return total
}

private fun eraseOverlapping(internals: Array<IntArray>): Int {
    if (internals.isEmpty()) {
        return 0
    }
    val size = internals.size
    Arrays.sort(internals, Comparator.comparingInt { o: IntArray ->
        o[1]
    })
    var total = 0
    var previous = internals[0][1]
    for (i in 1 until size) {
        if (internals[i][0] < previous) {
            total++
        } else {
            previous = internals[i][1]
        }
    }
    return total
}

fun partitionLabels(S: String): List<Int>? {
    val last = IntArray(26)
    for (i in S.indices) {
        last[S[i] - 'a'] = i
    }
    val result: MutableList<Int> = ArrayList()
    var j = 0
    var arch = 0
    for (i in S.indices) {
        j = j.coerceAtLeast(last[S[i] - 'a'])
        if (i == j) {
            result.add(i - arch + 1)
            arch = i + 1
        }
    }
    return result
}

fun maxProfit(prices: IntArray): Int {
    var profit = 0
    for (i in 1 until prices.size) {
        if (prices[i] > prices[i - 1]) {
            profit += prices[i] - prices[i - 1]
        }
    }
    return profit
}

fun reconstructQueue(people: Array<IntArray>): Array<IntArray>? {
    Arrays.sort(people) { o1: IntArray, o2: IntArray ->
        if (o1[0] == o2[0])
            o1[1] - o2[1]
        else o2[0] - o1[0]
    }
    val outputs = LinkedList<IntArray>()
    for (person in people) {
        outputs.add(person[1], person)
    }
    return outputs.toArray(Array(people.size) { IntArray(2) })
}

fun checkPossibility(nums: IntArray): Boolean {
    var fix = 0
    var i = 1
    while (i < nums.size && fix <= 1) {
        if (nums[i] >= nums[i - 1]) {
            i++
            continue
        }
        fix++
        if (i - 2 >= 0 && nums[i] < nums[i - 2]) {
            nums[i] = nums[i - 1]
        } else {
            nums[i - 1] = nums[i]
        }
        i++
    }
    return fix <= 1
}

fun merge(nums1: IntArray, m: Int, nums2: IntArray, n: Int) {
    var m = m
    var n = n
    var position = m-- + n-- - 1
    while (m >= 0 && n >= 0) {
        nums1[position--] = if (nums1[m] > nums2[n]) nums1[m--] else nums2[n--]
    }
    while (n >= 0) {
        nums1[position--] = nums2[n--]
    }
}